﻿//当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
//给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
//
//输入: n = 10
//输出 : 9
//
//输入 : n = 1234
//输出 : 1234
//
//输入 : n = 332
//输出 : 299
//
//提示 :
//	0 <= n <= 10^9

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n); // 把数字转化成字符串
        int i = 0, m = s.size();
        // 找第⼀个递减的位置
        while (i + 1 < m && s[i] <= s[i + 1])i++;
        if (i + 1 == m)
            return n; // 判断⼀下特殊情况
        // 回推
        while (i - 1 >= 0 && s[i] == s[i - 1])i--;
        s[i]--;
        for (int j = i + 1; j < m; j++)s[j] = '9';
        return stoi(s);
    }
};